1. Field of the Invention
This invention relates to computer science and communications engineering. More particularly, relates to an apparatus and method for generating sequences, such as Gold sequences, using a novel parallel architecture.
2. Description of the Prior Art
Modern integrated circuit products can contain several million transistors while dissipating power on the order of 20 watts. This high level of power dissipation prevents use of these circuits in applications with limited power Supply capacity, such as notebook computers, cellular phones and other portable computing and communication products. There is therefore a continuous need to further reduce the power consumption of integrated circuits, especially in systems operating at very fast clock frequencies. In portable computers, conventional nickel-cadmium batteries only provide 20 watt-hours of energy per pound. Improvements in battery technology are underway, but it is unlikely that spectacular increases in the energy-to-weight ratio will be realized in the very near future.
Even in non-portable applications, where up until now power could be dissipated by heat sinks and cooling fans, the density and size of chips and systems continues to increase, resulting in increased cooling requirements. Such increased power and cooling requirements cause difficulty in providing adequate cooling, that might add significant cost to systems, or that may limit the amount of functionality that can be provided.
It is evident that methods for decreasing the amount of power used by a circuit providing a given functionality are desirable for conserving battery power, for reducing cooling requirements, and for allowing increased functionality in state-of-the-art systems. Improvements are being made in circuit design and fabrication methods to reduce power requirements. Improved algorithms can also be developed to provide desired functionality with lower power requirements.
Digital codes and sequence generators are used extensively in communications, radar, navigation and computer disciplines. The types of systems in which they play a key role continue to increase due to advances in technology which favor the use of digital signal processing. Many of these applications must provide high computation rates but cannot incur the power consumption penalty associated with high clock frequencies. As digital coding techniques implemented by sequence generators are used in many of these applications, there is a need to increase the speed while reducing the power dissipation of such sequence generators.
A main use of digital sequences and codes is in the implementation of codes for information transmission and for error control and error detection. See, e.g., S. W. Golomb, Shift Register Sequences, Holden-Day, Inc., 1967; J. G. Proakis, Digital Communications, McGraw-Hill Book Co., 1989; W. W. Peterson and E. J. Weldon, Jr., Error Correcting Codes, The MIT Press, 1972; and J. E. Hershey and R. K. R. Yarlagadda, Data Transportation and Protection, Plenum Press, 1986. In particular, code or sequence generators are used in applications such as spread-spectrum communication systems, digital telephony systems, global positioning systems, and implementation of codes used for encryption and error correction systems.
The basic architectures of linear feedback shift registers are also used in many other applications, such as for generating a pseudo-random sequence or for the division of a train of pulses.
Up to the present, the conventional implementation of such sequence generators has been based on linear-feedback shift registers, wherein the registers are typically flip-flops. An example of such an implementation is shown in FIG. 1. See also U.S. Pat. No. 3,614,400, "Maximum Length Pulse Sequence Generators", which is incorporated herein by reference.
FIG. 1 shows the conventional architecture for using a linear feedback shift register to generate a digital sequence based on the polynomial x.sup.7 +x.sup.6 +x.sup.5 +x.sup.4 +1. This polynomial is selected as a representative formula which might be used. The length N of the shift register is determined by the highest degree of the polynomial, in this case seven. The locations of the taps 112 connected to shift register cells 110 correspond to the exponents that appear in the polynomial. Thus, in the illustrated case, there are four taps 112 connected to shift register cells 110, which are numbered "7", "6," "5" and "4". The values of the bits at these taps are added modulo two (exclusive OR operation) in logic circuitry 116, and the final resulting bit is fed back to the input, or shift register cell number "1", of the shift register through output line 114. At each clock pulse a new bit will be generated by the logic tree and presented at the input of the shift register cell number "1", while the bit in each shift register cell, which may be a flip-flop or other bi-stable memory device, is transmitted to the shift register cell on the right. The output sequence generated by such a shift register is typically taken from the feedback connection (the output of the logic tree), and is dependent upon the initial states of the N shift register cells, as bits past the taps, as in a conventional shift register implementation, in the present invention the taps are connected to the appropriate memory cells by a set of switches that selectively connect the taps to the proper memory cells in each cycle. Furthermore, in some embodiments, the present invention provides more than one member of the output sequence in each clock cycle, thus allowing sequence code to be supplied to other circuits at rates several times faster than the internal speed of the sequence generator itself.
A "tap exchange" method is provided that minimizes the number of switches necessary to implement a desired sequence generator, and that reduces the number of connections between the memory cells and the combinatorial logic, which may be an "exclusive-or" (XOR) tree. For a sequence generator having N registers or memory cells and M taps into the feedback logic, the number of switches can be reduced to the order of N+M.
In one embodiment, the present invention is a digital sequence generator, comprising a plurality of memory cells, each memory cell storing a bit of information in a digital format; logic circuitry having a plurality of inputs connectable to selected memory cells by tap switches, for generating an output based upon the contents of said memory cells; each of said tap switches for selectively connecting one of said memory cells to an input of said logic circuitry; and feedback circuitry for coupling the output of the logic circuitry to an input of a selected memory cell.
This invention, in a second embodiment, is a method of generating digital sequences, comprising providing a plurality of memory cells, logic circuitry for generating an output based upon contents of selected memory cells, Gap switches operable to connect selected memory cells to inputs of the logic circuitry, and feedback circuitry; closing selected tap switches to connect selected memory cells to input of the logic circuitry; calculating an output using said logic circuitry, said output being dependent upon the contents of the memory cells connected to said inputs of the logic circuitry, said output becoming one bit in the digital sequence being generated; and storing said output in a selected one of said memory cells using said feedback circuitry.
This invention, in a third embodiment is a digital sequence generator for generating two or more bits of a digital sequence simultaneously, comprising a plurality of memory cells, each memory cell storing a bit of information in a digital format; two or more logic circuitries, each logic circuitry having a plurality of inputs connectable to selected memory cells, each logic circuitry for generating an output based on the information stored in said memory cells; two or more tap switches, each tap switch for selectively connecting one of said memory cells to an input of a selected input of said logic circuitries; and feedback circuitry for selectively coupling the output of the logic circuitry to an input of a selected one of said memory cells.
This invention, in a fourth embodiment, is a parallel shift register, comprising: a plurality of digital storage cells, each digital storage cell adapted for storing a bit of information in digital format; input logic circuitry having a plurality of input lines connectable to selected digital storage cells by tap switches; output logic circuitry having one or more output lines connectable to selected memory cells by output switches; each of said tap switches for selectively connecting one of said digital storage cells to a selected first input of said first logic circuitry.
In a fifth embodiment, the invention is a parallel shift register employing a parallel architecture, comprising: a plurality of cells, each cell for storing a bit of digital information; input switches coupled to each of said cells for selectively providing digital information from an input line for storage in each of said well as the polynomial implemented in the logic tree. While this type of architecture is adequate to generate the desired sequence in a straight-forward way and with minimal hardware, it suffers from two major drawbacks: First, the complete structure must be switched or shifted in each clock cycle, thus dissipating a significant amount of power when clocked at a high rate or when using long shift registers, and second, only one bit of the output sequence is generated per clock cycle.
It is desirable, given the recent proliferation of battery powered computing and communication devices and the increasing clock speeds at which they operate, to provide an apparatus that can generate the same or similar sequences to those generated by the above-described shift register devices while utilizing less electrical energy. It is also desirable to generate such sequences several bits at a time (in parallel) so that the sequence bits may be generated at a rate faster than the internal clock rate of the sequence generator.